// 实现一个优先队列
// 小根堆，满足下面几个特性
// 1. 若父节点编号X，则子节点编号分别为2x和2x+1
// 2. 任意一个节点都小于它的子节点们，即堆序性。但同属于一个根的两个子节点，它俩互相没有左右顺序，只需都比父节点小就可以。
// 3. 完全二叉树

// 优先队列对外暴露出两个接口：1.入队 2.出队
// 入队：将一个新元素加入数组，且满足小根堆特性。假设元素叫X，入队时，先将其放在队列末端，然后让X和它的父元素(特性1)比较，如果比父元素小，就交换，如此往复
// 出队：将堆顶的元素弹出，即array.shift。同时，需仍旧满足3个特性，此时，应该从子元素中找一个更小的来填充，如此往复，这样操作到最后，可能会在最后一层不满足完全二叉树（因为数组元素个数虽然-1，但是后续元素只进行了位置交换，相当于这时数组的总数还没有变，那最终会多出一个空位），这时需要将最后一层的最后一个节点填充过来，填充过来时，相当于触发入队操作，再重新排序一次。

// 教程：https://www.bilibili.com/video/BV1mB4y1c7we/?spm_id_from=333.337.search-card.all.click&vd_source=4fd973d19cb5506a7c9f2d59e8ab5165

class PriorityQueue {
    // 优先队列构造器
    constructor(arr = []) {
        this.arr = arr;
        this.tree = [];
        this.init();
        this.debug = true;
    }

    /**
     * 入队
     * @param {*} 值
     * @param {*} 队列中的制定位置，默认放到最后
     * @returns
     */
    add(value, index = null) {
        if (index === null) {
            // 入队操作时，只需将元素放入数组最末端，然后和其父元素比较大小，如果比父元素小就交换位置即可
            this.tree.push(value);
        } else {
            if (this.tree[index] != null) {
                throw new Error(
                    `ERROR! PriorityQueue add: Can not insert value:${value} into index:${index}, index:${index} already has value: ${this.tree[index]}`
                );
            }

            this.tree[index] = value;
        }

        if (this.tree.length <= 1) {
            if (this.debug) {
                console.log(
                    `[pq add complete] value:${value}, tree:${JSON.stringify(
                        this.queue
                    )}`
                );
            }
            return;
        }

        let i = this.tree.length - 1 || index;
        while (i > 0) {
            const parentIndex = Math.floor((i - 1) / 2); // 父元素下标
            if (this.tree[parentIndex] <= this.tree[i]) break;
            this.swap(parentIndex, i);
            i = Math.floor((i - 1) / 2);
        }

        if (this.debug) {
            console.log(
                `[pq add complete] value:${value}, tree:${JSON.stringify(
                    this.queue
                )}`
            );
        }
    }

    /**
     * 出队 弹出堆顶的元素
     * @returns 弹出堆顶的元素
     */
    shift() {
        const ele = this.tree[0];
        this.tree[0] = null;

        // 重新排序优先队列
        // 将较小的那个子元素上移
        for (let i = 0; i < this.tree.length; ) {
            const leftIndex = i * 2 + 1;
            const rightIndex = leftIndex + 1;
            let finalIndex = null;

            let breakFlag = false;

            if (leftIndex >= this.tree.length) {
                break;
            }

            if (rightIndex >= this.tree.length) {
                breakFlag = true;
            }

            if (!breakFlag) {
                finalIndex =
                    this.tree[leftIndex] < this.tree[rightIndex]
                        ? leftIndex
                        : rightIndex;
            } else {
                finalIndex = leftIndex;
            }

            this.swap(i, finalIndex);

            if (breakFlag) break;

            i = finalIndex;
        }

        // 填充空位，然后删除最后一个元素
        let nullIndex = this.tree.findIndex((ele) => ele === null);
        let lastValue = this.tree.pop();
        if (nullIndex != this.tree.length) {
            this.add(lastValue, nullIndex);
        }
        return ele;
    }

    /**
     * 展示堆顶元素
     */
    peak() {
        return this.tree[0];
    }

    /**
     * 获取优先队列，排序方式按照广度排序(BFS)，从左到右，从上到下输出
     */
    get queue() {
        let ret = [];
        if (this.tree.length < 1) return ret;

        const depth = Math.floor(Math.log2(this.tree.length)) + 1;

        let arrIdx = new Array(depth).fill(true).map((_) => []);
        for (let level = 0; level < depth; level++) {
            if (level === 0) {
                ret.push(this.tree[0]);
                arrIdx[level].push(0);
                continue;
            }

            for (let j = 0; j < arrIdx[level - 1].length; j++) {
                const parentIndex = arrIdx[level - 1][j];
                const leftIndex = 2 * parentIndex + 1;
                const rightIndex = leftIndex + 1;

                let breakFlag = false;
                [leftIndex, rightIndex].every((index) => {
                    if (index < this.tree.length) {
                        ret.push(this.tree[index]);
                        arrIdx[level].push(index);

                        return true;
                    } else {
                        breakFlag = true;
                        return false;
                    }
                });

                if (breakFlag) break;
            }
        }

        return {
            tree: this.tree,
            ret,
        };
    }

    // 初始化优先队列
    init() {
        for (const ele of this.arr) {
            this.add(ele);
        }
    }

    // 交换节点顺序
    swap(index1, index2) {
        [this.tree[index1], this.tree[index2]] = [
            this.tree[index2],
            this.tree[index1],
        ];
    }
}

// 测试代码
console.log(`[PriorityQueue] test start`);
const minHeap = new PriorityQueue();
minHeap.add(8);
minHeap.add(2);
minHeap.add(15);
minHeap.add(5);
minHeap.add(4);
minHeap.add(45);

console.log(`[PriorityQueue] shift`);
let ele = minHeap.shift();
console.log(`[PriorityQueue] shift element:${ele}`);
